The invention analyzes a set of conditions with an expert knowledge base of rules using plural separate nodes which fire respective rules of said knowledge base, each of said rules upon being fired altering certain of said conditions predicated upon existence of others of said conditions, the invention operating by constructing a P representation of all pairs of said rules which are input dependent or output dependent; constructing a C representation of all pairs of said rules which are communication dependent or input dependent; determining which of the rules are ready to fire by matching the predicate conditions of each rule with the conditions of said set; enabling said node means to simultaneously fire those of the rules ready to fire which are defined by said P representation as being free of input and output dependencies; and communicating from each node enabled by said enabling step the alteration of conditions by the corresponding rule to other nodes whose rules are defined by said C matrix means as being input or communication dependent upon the rule of said enabled node.
Rule-based expert systems of the conventional type are implemented in a computer having a memory storing a knowledge base. The knowledge base is a set of rules, each defining a result predicated upon a specific set of conditions being met in a predetermined manner. Such rules are, in effect, a set of "If . . . , then . . ." statements. The predicate conditions upon which each rule is based (i.e., the "IF" clause of the rule) may be represented by computer-language statements. A set of actual conditions observed or measured which are to be analyzed by the expert system are stored as data in the working memory of the computer. In their simplest form, such conditions may be binary true/false data, for example. Whenever conditions called for in the IF clause of a rule are satisfied (or "true"), executing or "firing" the rule changes certain other conditions specified in the THEN clause of the rule, for example by changing such conditions from "false" to "true" or vice versa.
During the inferencing cycle, the first phase or step performed by the expert system is to attempt to match the predicate conditions (the IF clause) of each rule with the contents of the working memory. A rule is ready to be "fired" if all of its predicate conditions are met by the contents of the working memory. The next step is to identify any conflicts which may exist between the various rules which are ready to be fired and select the next rule to be fired. Two rules are conflicting if the result (THEN statement) produced by one rule affects conditions called for in the predicate (IF statement) of the other rule. Two rules are also conflicting if their results change the same condition differently. In either case, anomalous results would be obtained if the conflicting rules were fired using the same working memory contents. Various well-known techniques are used to select the "best" rule to be fired next. Then, all rules which do not conflict with the best rule may also be fired in rapid sequence thereafter without updating the contents of the working memory. In some techniques, not all of the non-conflicting rules are necessarily fired.
Such experts systems have been described, for example, in U.S. Pat. Nos. 4,837,735 (to Allen, Jr., et al.), 4,783,752 (to Kaplan et al.), 4,849,905 (to Loeb et al.), 4,847,784 (to Clancey), 4,809,219 (to Ashford et al.), 4,868,763 (to Masui et al.), 4,754,409 (to Ashford et al.) and 4,763,277 (to Ashford et al.).
United Kingdom published application number 2,207,531A discloses an expert system using similar techniques but which allocates execution of each of the rules to separate parallel processors or nodes. This type of parallel system is intended for achieving speedup in the match phase of the expert system inferencing cycle by storing the results of the matching phase in accordance with a Rete algorithm. However, such parallel processor systems have not achieved anticipated execution speed increases, and in fact have generally achieved only a five-fold speed increase over non-parallel or sequential implementations. This can be explained in part because such expert systems are written in serial languages and designed to exploit only obvious sources of parallelism.
One problem is that they achieve maximum speed (number of rule firings per cycle) only if there are many non-conflicting rules that can be fired without updating the working memory. After each cycle, the working memory must be updated from the results of each rule fired during the cycle and the next cycle begins by performing the matching phase and the conflict resolution and rule selection phase, a time consuming task.
A new approach is needed to out-perform parallel implementations (as exemplified in the above-referenced United Kingdom application) for knowledge bases containing hidden parallelism among rules, having high variable densities within rules, or exhibiting significant changes to working memory in individual inferencing cycles.
Accordingly, it is an object of the invention to exploit hidden parallelism among rules in an expert system.
It is a further object of the invention to provide a system which does not require performing conflict resolution tasks with each inferencing cycle.
It is another object of the invention to provide an expert system which does not perform the conflict resolution phases at run time.
It is a yet further object of the invention to provide a system which distributes the rule condition matching tasks among parallel nodes during the inferencing cycle, whereby it is unnecessary to use a Rete-based algorithm to store the results of the matching phase.
It is another object of the invention to provide an expert system which exploits hidden parallelism among rules and is faster than Rete algorithm-based parallel systems.
It is still another object of the invention to detect and analyze inter-rule dependencies to detect hidden parallelism prior to run time and to exploit this parallelism to achieve substantial increases in execution speed with respect to prior art systems.
It is a still further object of the invention to partially distribute the results of such analysis of inter-rule dependencies, the working memory of rule conditions, the knowledge base of rules and the inferencing cycle operation among nodes in an expert system.
It is yet another object of the invention to provide an expert system having intelligently interconnected nodes among which a knowledge of inter-rule dependencies is partially distributed.
These and other objects and benefits of the invention will become apparent from the detailed description given below when taken in conjunction with the accompanying drawings.